package leetcode.backtrace;

import java.util.*;

/**
 * @Description
 * @Author 26233
 * @Create 2021-04-01 21:32:50
 */

/*
n 皇后问题 研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。

给你一个整数 n ，返回所有不同的 n 皇后问题 的解决方案。

每一种解法包含一个不同的 n 皇后问题 的棋子放置方案，该方案中 'Q' 和 '.' 分别代表了皇后和空位。

 

示例 1：


输入：n = 4
输出：[[".Q..","...Q","Q...","..Q."],["..Q.","Q...","...Q",".Q.."]]
解释：如上图所示，4 皇后问题存在两个不同的解法。
示例 2：

输入：n = 1
输出：[["Q"]]
 

提示：

1 <= n <= 9
皇后彼此不能相互攻击，也就是说：任何两个皇后都不能处于同一条横行、纵行或斜线上。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/n-queens
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */

public class LeetCode51_SolveNQueens {

    public List<List<String>> solveNQueens(int n) {

        List<List<String>> result = new ArrayList<>();
        int[][] arr = new int[n][n];

        List<Integer[]> count = new ArrayList<>();

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                arr[i][j] = 1;
                count.add(new Integer[]{i, j});
                solveNQueens(arr, count);

                if (count.size() == arr.length){
                    printfArr(arr);
                    System.out.println("\n");
                }
                count.clear();
                arr = new int[n][n];
            }
        }

        return result;
    }

    public void solveNQueens(int[][] arr, List<Integer[]> count){
        if (count.size() == arr.length) return;
        for (int i = 0; i < arr.length; i++) {
            for (int j = 0; j < arr[0].length; j++) {
                if(check(i, j, count)){
                    arr[i][j] = 1;
                    count.add(new Integer[]{i, j});
                    solveNQueens(arr, count);
                }
            }
        }
    }

    boolean check(int m, int n, List<Integer[]> count){
        for (int i = 0; i < count.size(); i++) {
            if(count.get(i)[0] == m || count.get(i)[1] == n ||
                    (Math.abs(count.get(i)[0] - m) == Math.abs(count.get(i)[1] - n)))
                return false;
        }
        return true;
    }

    boolean checkR(int m, List<Integer[]> count){
        for (int i = 0; i < count.size(); i++) {
            if(count.get(i)[0] == m)
                return false;
        }
        return true;
    }
    boolean checkC(int n, List<Integer[]> count){
        for (int i = 0; i < count.size(); i++) {
            if(count.get(i)[1] == n)
                return false;
        }
        return true;
    }
    boolean checkRC(int m, int n, List<Integer[]> count){
        for (int i = 0; i < count.size(); i++) {
            if((Math.abs(count.get(i)[0] - m) == Math.abs(count.get(i)[1] - n)))
                return false;
        }
        return true;
    }

    void printfArr(int[][] arr){
        for (int i = 0; i < arr.length; i++) {
            for (int j = 0; j < arr[0].length; j++) {
                System.out.print(arr[i][j] + " ");
            }
            System.out.println();
        }
    }

    //////////////////////////////////
    public List<List<String>> solveNQueens2(int n) {

        List<List<String>> result = new ArrayList<>();
        List<Integer[]> count = new ArrayList<>();
        char[] s = new char[n * n];
        Arrays.fill(s, '.');
        Set<String> set = new HashSet<>();

        solveNQueens2(set, s, count, n, 0);

        List<String> tempResult;
        Iterator<String> iterator = set.iterator();
        String tempStr;
        while(iterator.hasNext()){
            tempResult = new ArrayList<>();
            tempStr = iterator.next();
            for (int j = 0; j < n; j++) {
                tempResult.add(tempStr.substring(j * n, j * n + n));
            }
            result.add(tempResult);
        }
        return result;
    }
    // 从上往下放置，row 参数来排除已放置的行
    public void solveNQueens2(Set<String> set, char[] s, List<Integer[]> count, int n, int row){
        if (count.size() == n) {
            set.add(new String(s));
            return;
        }
        for (int j = 0; j < n; j++) {
            if (!checkC(j, count)) continue;
            if(checkRC(row, j, count)){
                s[(row * n) + j] = 'Q';
                count.add(new Integer[]{row, j});
                solveNQueens2(set, s, count, n, row + 1);
                s[(row * n) + j] = '.';
                count.remove(count.size() - 1);
            }
        }
    }

    public static void main(String[] args) {
        int n = 9;
        // new LeetCode51_SolveNQueens().solveNQueens(n);
        new LeetCode51_SolveNQueens().solveNQueens2(n);
    }

}
